/**
 * 767. 重构字符串
 * https://leetcode-cn.com/problems/reorganize-string/
 */
public class Solutions_767 {
    public static void main(String[] args) {
//        String str = "aab";  // output: "aba"
//        String str = "aaab";  // output: ""
        String str = "vvvlo";  // output: "vlvov";

        String result = reorganizeString(str);
        System.out.println(result);
    }

    /**
     * 解题思路：计数法 + 奇偶穿插
     */
    public static String reorganizeString(String S) {
        if (S == null || S.length() < 2) {
            return "";
        }
        int[] countArr = new int[26];
        char[] sarr = S.toCharArray();
        int slen = sarr.length;
        char[] res = new char[slen];
        // 统计 S 中各字符的出现次数
        for (char c : sarr) {
            countArr[c - 'a'] ++;
        }
        // "vvvlo" 的情况，必须找到出现次数最多的字符，优先放置
        int maxIdx = 0;
        int maxCnt = 0;
        // 遍历 countArr，记录下最大出现次数的字符，及其出现次数
        for (int i = 0; i < countArr.length; i++) {
            if (countArr[i] > maxCnt) {
                maxCnt = countArr[i];
                maxIdx = i;
            }
        }
        if (maxCnt > (slen + 1) / 2) {
            // 出现次数大于数组长度一半：aaab 的情况，无法保证字符 a 不连续
            return "";
        }

        int idx = 0;
        while (countArr[maxIdx] > 0) {
            // 可以肯定，放置 countArr[max] 一定不会越界
            res[idx] = (char)(maxIdx + 'a');
            countArr[maxIdx] --;
            idx += 2;
        }
        // idx 索引一定不会越界，不做判断
        for (int i = 0; i < 26; i++) {
            while (countArr[i] > 0) {
                if (idx >= slen) {
                    // 偶数索引上放置完毕，开始放置奇数位置
                    idx = 1;
                }
                res[idx] = (char) (i + 'a');
                countArr[i] --;
                idx += 2;
            }
        }
        return String.valueOf(res);
    }
}
